#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

string minWindow(string s, string t) {
    if (s.size() < t.size()) {
        return "";
    }
    // 用于记录t中每个字符出现的次数
    unordered_map<char, int> target;
    // 用于记录当前窗口中每个字符出现的次数
    unordered_map<char, int> window;
    for (char c : t) {
        target[c]++;
    }

    int left = 0, right = 0;
    // 记录当前窗口中已经满足t的字符种类数
    int match = 0;
    // 记录最小子串的起始位置和长度
    int start = 0, minLen = INT_MAX;

    while (right < s.size()) {
        char c1 = s[right];
        if (target.count(c1)) {
            window[c1]++;
            if (window[c1] == target[c1]) {
                match++;
            }
        }
        right++;

        while (match == target.size()) {
            if (right - left < minLen) {
                minLen = right - left;
                start = left;
            }
            char c2 = s[left];
            if (target.count(c2)) {
                window[c2]--;
                if (window[c2] < target[c2]) {
                    match--;
                }
            }
            left++;
        }
    }

    if (minLen == INT_MAX) {
        return "";
    }
    return s.substr(start, minLen);
}